\documentclass{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color} % For colors and names
\title{Laboratorium Rozpoznawania Obrazów \\ ćwiczenie 2: klasyfikacja optymalna Bayesa} % Title

\author{Tomasz \textsc{Bawej}} % Author name

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{language=Verilog, tabsize=3, backgroundcolor=\color{mygrey}, basicstyle=\small, commentstyle=\color{BrickRed}}
\lstset{ 
	language=[ISO]C++,              % choose the language of the code ("language=Verilog" is popular as well)
   tabsize=3,							  % sets the size of the tabs in spaces (1 Tab is replaced with 3 spaces)
	basicstyle=\scriptsize,               % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\scriptsize,              % the size of the fonts that are used for the line-numbers
	stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{mygrey}, % choose the background color. You must add \usepackage{color}
	%showspaces=false,              % show spaces adding particular underscores
	%showstringspaces=false,        % underline spaces within strings
	%showtabs=false,                % show tabs within strings adding particular underscores
	frame=single,	                 % adds a frame around the code
	tabsize=3,	                    % sets default tabsize to 2 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	%escapeinside={\%*}{*)},        % if you want to add a comment within your code
	commentstyle=\color{BrickRed}   % sets the comment style
}

\begin{document}

\maketitle % Insert the title, author and date

%\begin{tabular}{lr}
%Date Performed: 1/1/2012 & Partner: James Smith\\ % Date the experiment was performed and partner's %name
%Instructor: Mary Jones % Instructor/supervisor
%\end{tabular}

\setlength\parindent{0pt} % Removes all indentation from paragraphs

\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

\section{Cel}

Zapoznanie się z klasyfikacją Bayesa przy różnych metodach liczenia wartości funkcji gęstości prawdopodobieństwa. Implementacja oraz porównanie stosownych klasyfikatorów z~wykorzystaniem środowiska \textit{Octave}.



% If you have more than one objective, uncomment the below:
%\begin{description}
%\item[First Objective] \hfill \\
%Objective 1 text
%\item[Second Objective] \hfill \\
%Objective 2 text
%\end{description}
 
\section{Założenia}
Za punkt wyjściowy przedstawionych rozwiązań przyjęto sytuację, w której dane treningowe i~testowe są~już wczytane z odpowiednich plików oraz pozbawione przekłamanych próbek.

\section{Koncepcja rozwiązania}

Funkcją spajającą zaimplementowane klasyfikatory jest funkcja \textit{launcher}, przyjmująca kolejno następujące parametry:
\begin{itemize}
\item nazwa metody (\textit{coreTask1}. \textit{coreTask2} lub \textit{coreTask3})
\item zbiór danych treningowych
\item zbiór danych testowych
\item minimalna liczność podzbioru atrybutów użytych do klasyfikacji
\item maksymalna liczność podzbioru atrybutów użytych do klasyfikacji
\item początek zakresu kolumn stanowiących zbiór atrybutów (w odniesieniu do~wejściowych zbiorów danych, domyślnie 2)
\item koniec zakresu kolumn stanowiących zbiór atrybutów (w odniesieniu do~wejściowych zbiorów danych, domyślnie 8)
\item wektor szerokości okna (brany pod uwagę jedynie dla \textit{coreTask3}, domyślnie [0.01,0.001,0.0001])
\end{itemize}

Funkcja \textit{launcher} pozwala wsadowo trenować i odpytywać klasyfikatory o różnych parametrach. Generuje ona wszystkie podzbiory atrybutów próbek (zgodne z zadanymi parametrami), na podstawie których przeprowadza następnie trening i testowanie klasyfikatora (funkcje \textit{coreTask*}). Wartości prawdopodobieństwa \textit{a priori} w poszczególnych klasach szacowane są na podstawie zawartości zbioru testowego. Wyniki przeprowadzanych testów są na bieżąco wyświetlane na konsoli.\\

Funkcje \textit{coreTask1}, \textit{coreTask2} oraz \textit{coreTask3} odpowiedzialne są za realizację procesu uczenia oraz testowania klasyfikatora. Zgodnie z założeniami ćwiczenia, funkcje te różnią się sposobem wyznaczania wartości funkcji gęstości prawdopodobieństwa dla klasyfikowanej próbki względem każdej z klas 1-4. Funkcja \textit{coreTask1} wyznacza tę wartość jako iloczyn wartości dla każdej z cech, \textit{coreTask2} wyznacza wartość \textit{n}-wymiarowej funkcji gęstości prawdopodobieństwa, podczas gdy \textit{coreTask3} aproksymuje poszukiwaną wartość na podstawie wartości próbki oraz przykładów stanowiących reprezentację każdej z klas w zbiorze treningowym.
\\
Funkcje \textit{coreTask*} charakteryzują się ujednoliconym interfejsem, w ramach którego jako kolejne atrybuty przekazywane są:
\begin{itemize}
\item zbiór danych treningowych, interpretowany jako zbiór wierszy, których pierwsza wartość jest etykietą klasy, a kolejne wartościami atrybutów używanych do klasyfikacji
\item zbiór danych testowych w postaci identycznej do danych treningowych
\item wektor wierszowy prawdopodobieństw \textit{a priori} dla klas 1-4 (domyślnie [0.25, 0.25, 0.25, 0.25])
\item (jedynie dla \textit{coreTask3}) szerokość okna (domyślnie 0.001)
\end{itemize}

Funkcje \textit{coreTask*} jako wynik działania zwracają macierz opisującą proces testowania klasyfikatora. Pierwszy wiersz takiej macierzy zawiera kolejno liczby próbek każdej z klas 1-4, które były klasyfikowane w ramach testu. Drugi wiersz zawiera liczbę błędnie sklasyfikowanych przykładów w każdej z klas.
\subsection*{Funkcje pomocnicze}
\begin{itemize}
\item Funkcja \textit{coreTask1} korzysta z dodatkowych funkcji: \textit{getMeans} i \textit{getStdevs} (dla uzyskania parametrów rozkładów w klasach) oraz funkcji \textit{performTest} i \textit{guessClass} (dla odpytania klasyfikatora o próbki ze zbioru testowego)
\item Funkcja \textit{coreTask2} korzysta z funkcji \textit{mvnpdf} pakietu \textit{statistics}
\item Funkcja \textit{coreTask3} korzysta z funkcji \textit{window} (wyznaczenie wartości funkcji okna), \textit{distance} (miara odległości dwóch wektorów w \textit{n}-wymiarowej przestrzeni) oraz \textit{parzen} (dla określenia wartości funkcji gęstości prawdopodobieństwa dla danej próbki względem określonej klasy reprezentowanej przez zbiór przykładów)
\item Dodatkową funkcją pomocniczą jest \textit{reduceSet}, która pozwala zredukować zbiór danych do pożądanego rozmiaru, umożliwiając określenie proporcji, w jakich w skład nowego zbioru wejdą próbki z poszczególnych klas.

\end{itemize}

\section{Wyniki i wnioski}
\subsection{Klasyfikator optymalny Bayesa przy równych prawdopodobieństwach \textit{a priori}}
Dla atrybutów z kolumn 2 i 4 oraz \textit{train} i \textit{test} będących kolejno pełnym zbiorem treningowym oraz pełnym zbiorem testowym otrzymano:
\begin{lstlisting}
octave:42> r=coreTask1(train(:,[1,2,4]),test(:,[1,2,4]))
r =

   456   456   455   456
   238     4     2    75

octave:43> r=coreTask2(train(:,[1,2,4]),test(:,[1,2,4]))
r =

   456   456   455   455
    55     4     1    11

octave:44> r=coreTask3(train(:,[1,2,4]),test(:,[1,2,4]))
r =

   456   456   455   456
     3     0     1    10
     
\end{lstlisting}
Gdzie macierz wynikowa zawiera informacje o liczbie próbek testowych oraz błędnie sklasyfikowanych próbkach w poszczególnych klasach.

\subsection{Wpływ liczności zbioru treningowego na wyniki klasyfikacji}
Podstawowe testy w tym zakresie przeprowadzono generując losowe podzbiory zbioru treningowego (z zachowaniem proporcji klas - funkcja \textit{reduceSet}), które następnie wykorzystywane były jako zbiór trenujący. Tym sposobem na każdym z poziomów (0.5, 0.25, 0.10 liczności początkowego zbioru treningowego) przeprowadzono co najmniej pięć prób dla każdej z metod. Do klasyfikacji wykorzystano te same atrybuty, co w poprzednim podpunkcie.

Zaobserwowane zmiany jakości klasyfikacji miały różny charakter, w zależności od sposobu klasyfikacji:
\begin{itemize}
\item Dla metody zakładającej niezależność cech jakość klasyfikacji zachowywała się najmniej przewidywalnie wraz ze zmniejszaniem zbioru trenującego. Np. dla zbioru o liczności 0.1 całego zbioru trenującego, w zależności od~wylosowanego podzbioru trenującego, współczynnik błędu wyniósł od~0.14 do 0.23 (przy 0.175 dla pełnego zbioru treningowego).
\item Metoda wykorzystująca wielowymiarowy rozkład normalny okazała się o~wiele bardziej stabilna, chociaż i w jej przypadku odchudzenie zbioru trenującego mogło zaowocować poprawą jakości klasyfikacji. Przeciętna jakość klasyfikacji wykazała ostatecznie lekko zaszumioną tendencję spadkową wraz ze zmniejszaniem zbioru trenującego. Spadek jakości (pomiędzy pełnym zbiorem a 0.1 zbioru) nie przekroczył jednak w tym wypadku 0.01.
\item Metoda wykorzystująca okno Parzena wykazała się największą stabilnością - współczynnik błędu rósł stale wraz ze zmniejszaniem zbioru treningowego, osiągając przeciętne wartości na poziomie 0.007 dla pełnego zbioru, 0.016 dla połowy zbioru, 0.027 dla 0.25 zbioru oraz 0.036 dla 0.1 zbioru.
\end{itemize}

\subsection{Wsadowe badanie klasyfikatorów z oknem Parzena}
Korzystając z funkcji \textit{launcher} sprawdzono skuteczność klasyfikatora z oknem Parzena dla wszystkich podgrup atrybutów o liczności od 2 do 4 przy wartościach szerokości okna ze zbioru: 0.01, 0.001, 0.0001. Za zbiór treningowy obrano losowo wygenerowany podzbiór stanowiący 0.1 oryginalnego zbioru treningowego z zachowaniem proporcji pomiędzy klasami próbek. Opisany eksperyment ilustruje poniższy wydruk.
\begin{lstlisting}
t=reduceSet(train,0.1);
octave:182> launcher("coreTask3",t,test,2,4,2,8,[0.01,0.001,0.0001])
   0.25014   0.25014   0.24959   0.25014
...
colset: 2   4 \ errors rate: 0.17663 \ h1=0.01
colset: 2   4 \ errors rate: 0.044981 \ h1=0.001
colset: 2   4 \ errors rate: 0.1898 \ h1=0.0001
...
colset: 3   4 \ errors rate: 0.24794 \ h1=0.01
colset: 3   4 \ errors rate: 0.023587 \ h1=0.001
colset: 3   4 \ errors rate: 0.0082282 \ h1=0.0001
...
colset: 2   3   4 \ errors rate: 0.17224 \ h1=0.01
colset: 2   3   4 \ errors rate: 0.013165 \ h1=0.001
colset: 2   3   4 \ errors rate: 0.2463 \ h1=0.0001
...
colset: 3   4   5 \ errors rate: 0.24849 \ h1=0.01
colset: 3   4   5 \ errors rate: 0.023587 \ h1=0.001
colset: 3   4   5 \ errors rate: 0.0054855 \ h1=0.0001
...
colset: 3   4   5   6 \ errors rate: 0.24849 \ h1=0.01
colset: 3   4   5   6 \ errors rate: 0.023587 \ h1=0.001
colset: 3   4   5   6 \ errors rate: 0.0054855 \ h1=0.0001
colset: 3   4   5   7 \ errors rate: 0.24849 \ h1=0.01
colset: 3   4   5   7 \ errors rate: 0.023587 \ h1=0.001
colset: 3   4   5   7 \ errors rate: 0.0054855 \ h1=0.0001
colset: 3   4   5   8 \ errors rate: 0.24849 \ h1=0.01
colset: 3   4   5   8 \ errors rate: 0.023587 \ h1=0.001
colset: 3   4   5   8 \ errors rate: 0.0054855 \ h1=0.0001
...
Elapsed time is 6452.2 seconds.

\end{lstlisting}
Z powyższego wydruku wynika, iż generalnie lepsze wyniki klasyfikacji uzyskano dla mniejszych wartości szerokości okna. Wyjątek stanowi jednak przypadek najlepszego wyniku klasyfikacji wg dwóch parametrów.


\subsection{Poszukiwanie najlepszego zestawu cech}
O ile w przypadku klasyfikatora z oknem Parzena jakość klasyfikacji dla poszczególnych zestawów cech  zależy jeszcze przynajmniej od szerokości okna, a~operowanie na całości zbioru treningowego jest bardzo czasochłonne, o tyle dla dwóch pozostałych klasyfikatorów można pokusić się o wyznaczenie optymalnego podzbioru cech dla klasyfikacji z wykorzystaniem całego zbioru treningowego.
Poniżej zamieszczono listingi prezentujące przeprowadzone w tym celu czynności oraz kwintesencję uzyskanych wyników.
\begin{lstlisting}
octave:6> launcher("coreTask1",train,test,2,7)
   0.25014   0.25014   0.24959   0.25014
colset: 2   3 \ errors rate: 0.15853
...
colset: 2   3   4 \ errors rate: 0.13659
colset: 2   3   5 \ errors rate: 0.1333
...
colset: 2   3   4   5 \ errors rate: 0.12946
...
colset: 2   3   4   5   7 \ errors rate: 0.12891
...
colset: 2   3   4   5   6   7 \ errors rate: 0.12891
...
colset: 2   3   4   5   6   7   8 \ errors rate: 0.13659
Elapsed time is 938.41 seconds.
\end{lstlisting}

Jak wynika z powyższego wydruku, dla pierwszego typu klasyfikatora da~się poprawić jakość klasyfikacji poprzez uwzględnienie kolejnych wymiarów, jednak poprawa ta nie jest znaczna i nie zachodzi dla klasyfikacji z użyciem 5 i więcej atrybutów.

\begin{lstlisting}
octave:8> launcher("coreTask2",train,test,2,7);
   0.25014   0.25014   0.24959   0.25014
colset: 2   3 \ errors rate: 0.16026
colset: 2   4 \ errors rate: 0.038968
...
colset: 2   3   4 \ errors rate: 0.00054885
...
colset: 2   3   4   5 \ errors rate: 0.00054885
colset: 2   3   4   6 \ errors rate: 0.00054885
...
colset: 2   3   4   5   6 \ errors rate: 0.00054885
colset: 2   3   4   5   7 \ errors rate: 0.00054885
...
colset: 2   3   4   5   6   7 \ errors rate: 0.00054885
...
colset: 2   3   4   5   7   8 \ errors rate: 0.00054885
...
colset: 2   3   4   5   6   7   8 \ errors rate: 0.00054885
Elapsed time is 488.64 seconds.
\end{lstlisting}

W przypadku klasyfikatora korzystającego z wielowymiarowego rozkładu prawdopodobieństwa wykorzystanie wszystkich wymiarów daje natomiast najlepszy możliwy wynik, aczkolwiek osiągalny już dla odpowiedniej kombinacji 3 atrybutów.

\subsection{Zmiana prawdopodobieństw \textit{a priori}, a zmiana wyników klasyfikacji}
W wyniku zmiany prawdopodobieństw \textit{a priori} klasyfikator winien faworyzować klasy "czerwone". Zachowanie to uwidacznia się szczególnie w przypadku klasyfikatorów charakteryzujących się znacznym odsetkiem błędów. Dla tej grupy klasyfikatorów maleje odsetek błędnie sklasyfikowanych próbek "czerwonych" kosztem błędnie klasyfikowanych pików i trefli. W przypadku bardziej stabilnych i wiarygodnych klasyfikatorów zmiana może być niezauważalna, gdyż prawdopodobieństwa odpowiadają faktycznym proporcjom zbioru testowego, a jakość rozróżniania klas na podstawie wartości funkcji gęstości prawdopodobieństwa może łagodzić wpływ preferencji podyktowanej prawdopodobieństwem \textit{a priori}. Poniżej zaprezentowano wynik klasyfikacji w poszczególnych klasach dla metody wykorzystującej wielowymiarowy rozkład prawdopodobieństwa oraz dwa różne zestawy atrybutów. 
\begin{lstlisting}
octave:185> test2=reduceSet(test,0.5,[0.33,0.33,0.17,0.17])

octave:186> coreTask2(train(:,[1,2,3]),test(:,[1,2,3]))
ans =

   456   456   455   455
    34     0    31   227

octave:187> coreTask2(train(:,[1,2,3]),test2(:,[1,2,3]),[0.33,0.33,0,0.17,0.17])
ans =

   299   300   154   154
     3     0   154    74

octave:188> coreTask2(train(:,[1,2,4,5]),test(:,[1,2,4,5]))
ans =

   456   456   455   455
     1     3     1     0

octave:189> coreTask2(train(:,[1,2,4,5]),test2(:,[1,2,4,5]),[0.33,0.33,0.17,0.17])
ans =

   299   300   154   154
     0     2     0     0

\end{lstlisting}
\subsection{Porównanie do klasyfikatorów 1-NN}
Zbudowane klasyfikatory cechują się możliwością osiągnięcia lepszych wyników, niż w przypadku klasyfikatorów 1-NN. Aby jednak faktycznie tak było, założony rozkład prawdopodobieństwa musi odpowiadać faktycznemu, lub być dobrze aproksymowanym. W przeciwnym razie trafność klasyfikacji może być na~poziomie tej, jaką udało się osiągnąć dla klasyfikatora opartego o nader optymistyczne założenia o niezależności cech oraz ich normalnym rozkładzie. 
%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

%\begin{thebibliography}{9}

%\bibitem{Smith:2012qr}
%Smith, J.~M. and Jones, A.~B. (2012).
%\newblock {\em Chemistry}.
%\newblock Publisher, City, 7th edition.

%\end{thebibliography}

\end{document}